//给定一个二叉树 root ，返回其最大深度。 
//
// 二叉树的 最大深度 是指从根节点到最远叶子节点的最长路径上的节点数。 
//
// 
//
// 示例 1： 
//
// 
//
// 
//
// 
//输入：root = [3,9,20,null,null,15,7]
//输出：3
// 
//
// 示例 2： 
//
// 
//输入：root = [1,null,2]
//输出：2
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数量在 [0, 10⁴] 区间内。 
// -100 <= Node.val <= 100 
// 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 2002 👎 0


//leetcode submit region begin(Prohibit modification and deletion)



/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        //后序遍历的应用
        //1. 递归方式
//        if(root == null)
//            return 0;
//        if(root.left == null && root.right == null)//递归结束条件,叶子节点（没有子节点）
//            return 1;
//        //有子节点的节点
//        int leftDepth = maxDepth(root.left);
//        int rightDepth = maxDepth(root.right);
//        return Integer.max(leftDepth, rightDepth) +1;//root节点层数为1
        //2. 栈
//        这套课程绝对是研究生的课
//        //2. 非递归方式实现后序遍历查找树的最大深度
////        > 2025/08/09 20:22:07
////        解答成功:
////        执行耗时:2 ms,击败了2.20% 的Java用户
////        内存消耗:42 MB,击败了8.88% 的Java用户
//        TreeNode curr = root;
//        TreeNode pop = null;
//        int max = 0;
//        LinkedList<TreeNode> stack = new LinkedList<>();
//        while(curr != null || !stack.isEmpty()){
//            if(curr!=null){
//                stack.push(curr);
//                int size = stack.size();
//                max = max<size?size:max;
//                curr = curr.left;
//            }else{
//                TreeNode peek = stack.peek();
//                if(peek.right == null || peek.right == pop){
//                    pop = stack.pop();
//                }else{
//                    curr = peek.right;
//                }
//            }
//        }
//        return max;
        //3. 层序遍历 队列（层数即最大高度）
        if(root == null) //leetcode需要加一下这个判断，否则会报空指针异常
            return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int currentLevel = 0;//当前层次
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0; i<size; i ++){
                TreeNode poll = queue.poll();
//            System.out.println(poll.val); 可输出当前层的各个元素
                if(poll.left != null)
                    queue.offer(poll.left);
                if(poll.right!=null)
                    queue.offer(poll.right);
            }
            currentLevel ++;
        }
        return currentLevel;



    }
}
//leetcode submit region end(Prohibit modification and deletion)
